package taller2.model.graph.algorithms;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

import taller2.interfaces.Connection;
import taller2.interfaces.Graph;
import taller2.interfaces.InitialNodeApplicator;
import taller2.interfaces.Node;
import taller2.model.graph.GraphImpl;
import taller2.utils.Constants;


//Class used for the Dijkstra algorithm on supervised mode. 

public class DijkstraApplicator extends AlgorithmApplicatorImpl implements InitialNodeApplicator{
	private static final String path = Constants.savedGraphsPath + "Dijkstra";	

	private int initialNode;
	private GraphImpl graph;
	Node start;
	private HashMap<String, Boolean> visitados;
	private HashMap<String, Float> distancias;
	private PriorityQueue<Tupla> cola;
	private int cont;
	
	public DijkstraApplicator(){
		super();
		cont = 0;
	}
	
	public void solveProblem(Graph g){
		
		if(noGraph(g) || !noGraphPaths() || !noPseudocodeLines())
			return;
		
		//si tiene aristas negativas dijkstra no funciona (por definicion!)
		if (hasNegativeEdges(g)){
			auxText.add("Error! Dijkstra can only be applied to graphs without negative edges!");
			return;
		}
		
		
		auxText.add("Inicia el algoritmo");
		
		g.killFluxes();
        visitados = new HashMap<String, Boolean>();
        distancias = new HashMap<String, Float>();
        cola = new PriorityQueue<Tupla>();

    	graph = null;
    	if (g != null) 
    		graph = (GraphImpl) g;
    	
    	start = null;
    		
    	// busco el nodo inicial 
    	ArrayList<Node> nodes = g.getNodes();

		int startIndex = initialNode;
		if (startIndex != -1){
			start = nodes.get(startIndex);	        
		}else{
			start = g.getFirstNode();	
			startIndex = 0;
		}
    		
		for(Node n: graph.getNodes()){
			n.setMarker("inf");
			n.mark();
		}
		    	
		graph.unselectConnections();		
		graph.unselectNodes();
			
		//Salvo estado inicial
	    saveGraph(graph,path);
	        
			
	    guardarPaso(graph, 0, false);
				        
		distancias.put(start.getID(),new Float(0));
		cola.add(new Tupla(start, 0)); 
	        
		start.unselect();
		start.setMarker("0");
		start.mark();
		
		guardarPaso(graph, 1, true);
	        
	    while (!cola.isEmpty()){
			guardarPaso(graph, 2, false);
				
			Tupla tupla = cola.poll();
			Node nodo = tupla.getNode();
	            
			guardarPaso(graph, 3, false);
				
	    	if (visitados.containsKey(nodo.getID())){ 				
	    		guardarPaso(graph, 4, false);
	            	
	            continue;  
	    	}
	    	float distancia = tupla.getDistancia() ;
	            
	        visitados.put(nodo.getID(), true);
	        nodo.select();
			guardarPaso(graph, 5, false);
		       
			for (Connection connection : nodo.getConnections()) {
				Node otroNodo;
				
				otroNodo = connection.getOtherNode();
				if (visitados.containsKey(otroNodo.getID()))
						continue;

			    	guardarPaso(graph, 6, false);

					Float distancia_otro = distancias.get(otroNodo.getID());

					if (distancia_otro == null || distancia_otro > distancia + connection.getWeight()) {
						distancias.put(otroNodo.getID(), distancia + connection.getWeight());

					guardarPaso(graph, 9, false);
					
					String nuevoPeso = String.valueOf(distancia	+ connection.getWeight());

					otroNodo.setMarker(nuevoPeso);
					otroNodo.mark();
				    guardarPaso(graph, 10, true);
					
					cola.add(new Tupla(otroNodo, distancias.get(otroNodo.getID())));

				    guardarPaso(graph, 11, false);
					
				}

			}
		}

	    guardarPaso(graph, 12, false);		
			
		for(Node targetNode:g.getNodes()){
			g.unselectConnections();
				
			if(!targetNode.equals(start))
				selectConnections(targetNode);			
				
		    guardarPaso(graph, 13, false);
		}

	    guardarPaso(graph, 15, false);
			
		//Listo!, se ejecuto el algoritmo -> cargo el estado inicial para empezar a mostrarlo
		graph.load(path);
	}

	private boolean hasNegativeEdges(Graph g) {
		for (Node node : g.getNodes()) {
			for (Connection conn: node.getConnections()){
				if (conn.getWeight() < 0){
					return true;
				}
			}
		}
		
		return false;
	}

	//para marcar los caminos desde start al nodo pasado por parametro
	private void selectConnections(Node node) {
		//si hay algun camino posible el nodo tiene valor distinto de infinito
		if (node.getMarker().compareTo("inf") != 0) {
			
			Node act = node;
			Connection conn = null;
			float weight = -1;
			while (weight != 0) {
				weight = -1;
				//arma el camino al reves: agarra el ultimo nodo y pide conexiones hacia el
				ArrayList<Connection> connections = graph.getConnectionsTo(act);

				for (Connection connection : connections) {
					//System.out.printf("\n%s\n",node1.getMarker());

					/*para la conexion con menor peso Y distinta de infintio
					 *  que parta de otro nodo (o sea hacia el ultimo del camino)...
					 */
					Node nodeAnteriorEnCamino = connection.getThisNode();
					
					if (nodeAnteriorEnCamino.getMarker().compareTo("inf") != 0) {
						//tengo que verificar porque no puede convertir magicamente "inf" a MAXINT o lo que sea.
						float actualWeight = Float.valueOf(nodeAnteriorEnCamino.getMarker()); //nota al margen: llamarlo "peso actual" cuando "actual" existe en ingles con otro significado es mala idea
						boolean esMenor = (weight == -1)
								|| (weight > actualWeight);
						if (esMenor) {
							act = nodeAnteriorEnCamino;
							weight = actualWeight;
							conn = connection;
						}
					}
					

				}

				//...se la selecciona
				if (conn != null) {
					conn.select();
				} else {
					break;
				}
			}
		}

	}
	
	private void guardarPaso(Graph g, int pcLine, boolean lineaNueva){

		saveGraph(g, path + cont);
		pseudocodeLines.add(pcLine);
		
		if (lineaNueva){
			String matrizActualizada = agregarLinea();
			auxText.add( matrizActualizada );
		}else{
			auxText.add( auxText.get( auxText.size() - 1 ) );
		}
		
		cont++;
		return;
	}
	
	private String agregarLinea(){
		String aDevolver = "";
		
		if (auxText.get( auxText.size() - 1 ).compareTo("Inicia el algoritmo") == 0){
			aDevolver = "";
		}else{
			aDevolver = auxText.get( auxText.size() - 1 ) + " \n";
		}
		
		for(Node n: graph.getNodes()){
			if (n.getMarker().compareTo("inf") == 0){
				aDevolver += "inf	";
			}else{
				aDevolver += n.getMarker().toString() + "	";
			}
		}
		
		return aDevolver;
	}
	
    public String getAuxText(){
    	if(auxText == null || auxText.isEmpty())
    		return "";
    	
    	return auxText.get(position);
    }
	
	public void setInitialNode(int selectedNode) {
		initialNode = selectedNode; 
	}
	
	public String getStartingGraphPath() {
		if(graphPaths == null || graphPaths.isEmpty())
			return "";
		return graphPaths.get(0);
	}
	
	@Override
	public int getHighlightedWordNumber() {
		return -1;
	}

	public String getGraphSol(int delta) {
		int tam = graphPaths.size();

		if(tam < delta+1)
			return "";

		return graphPaths.get(tam-delta-1);
	}

	public int getStartingNodePosition() {
		return initialNode;
	}

	@Override
	public void save(String path) {		
	}

	@Override
	public void load(String path) {
	}
	
	
	class Tupla implements Comparable<Tupla> {
	    private Node nodo;
	    private float distancia;

	    public Tupla(Node nodo, float distancia){

	        this.distancia = distancia;
	        this.nodo = nodo;
	    }

	    public int compareTo(Tupla otra){
	        if (distancia == otra.distancia)
	            return 0;
	        if (distancia < otra.distancia)
	            return -1;
	        return 1;
	    }

	    public Node getNode(){
	        return nodo;
	    }
	    public float getDistancia(){
	        return distancia;
	    }

	}
	
}
	
	
	




